package likou.tanxin;

/**
 * @author: Tangxz
 * @email:1171702529@qq.com
 * @cate: 2020/11/03 08:30
 */
//重构字符串
//给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
//若可行，输出任意可行的结果。若不可行，返回空字符串。
public class _767 {
    public String reorganizeString(String S) {
        int length = S.length();
        if (length == 1) {
            return S;
        }
        int[] arr = new int[26];
        int max_length = 0;
        for (char c : S.toCharArray()) {
            if (max_length < ++arr[c - 'a']) {
                max_length = arr[c - 'a'];
            }
        }

        if (max_length > (length+1)/2) return "";
        char[] ret = new char[S.length()];
        int even = 0, odd = 1;
        for (int i = 0; i < 26; i++) {
            while (arr[i] > 0 && arr[i] < (length/2 + 1) && odd < length) {
                ret[odd] = (char) (i + 'a');
                arr[i]--;
                odd += 2;
            }
            while (arr[i] > 0) {
                ret[even] = (char)(i + 'a');
                arr[i]--;
                even += 2;
            }
        }
        return new String(ret);
    }
}
